Electronic components include transistors, resistors, capacitors, and so on. Transistors come in various types (e.g., NMOS transistors, PMOS transistors, etc.). Electronic components may be connected to form an electronic circuit. Electronic circuits may be constructed to perform an analog function or a digital function. Electronic circuits are often integrated onto one piece of semiconductor material. Such a circuit is commonly referred to as an integrated circuit. Integrated circuits come in various forms such as custom designs, standard cell designs, gate array, field programable gate arrays, and so on.
A list of the electronic components that make up an integrated circuit is often useful for testing, debugging, archiving, and so on. The vast majority of integrated circuits manufactured today implement a digital circuit. Digital circuits may be constructed using just transistors. Therefore, a description of the transistors used in an integrated circuit and how they are connected together may fully describe the integrated circuit. Such a description is often referred to as a transistor-level netlist.
Initially, integrated circuits included a small number of transistors. Such integrated circuits are referred to as small scale integration (SSI). As the number of transistors increased, a number of levels of integration were crossed (e.g., medium scale integration (MSI), large scale integration (LSI), very large scale integration (VLSI), etc.). As the number of transistors grew, it became increasingly more difficult to convey the function of an integrated circuit by describing transistor connectivity. The level of abstraction was too low. A person viewing a dense transistor-level netlist may become overwhelmed with the details and lose sight of the big picture. It is not uncommon to have an integrated circuit contain over one million transistors. Trying to determine the functionality of such a circuit based on a transistor-level netlist would be very difficult, time-consuming, tedious, and prone to error. A higher level of abstraction is needed to describe such electronic circuits.
PMOS and NMOS transistors may be arranged to form all of the digital logic functions, or gates, such as the NAND gate, the NOR gate, the XNOR gate, etc. Digital logic gates are used to construct the vast majority of integrated circuits being manufactured today. Four, six, eight, or more transistors may be required to implement a particular gate. An abstraction was created for each gate so that a transistor-level description was no longer required to describe a gate. Gate-level abstractions may also be used to describe higher-level circuits (e.g., FLIP-FLOP, central processing unit, arithmetic logic unit, etc.). A higher-level circuit may be referred to as a macro.
Various computer-aided design tools have been created to quickly and accurately analyze an integrated circuit based on a transistor-level netlist and the physical implementation, or layout, of the integrated circuit. In many instances, the layout of the integrated circuit is not available. It may have been lost, never generated, or unavailable to a person doing reverse engineering. So, there is a need for a method of recovering a gate-level netlist from a transistor-level netlist of an integrated circuit where layout information of the gates included on the integrated circuit is unknown. The present invention is such a method.
U.S. Pat. No. 5,734,572, entitled "TOOL WHICH AUTOMATICALLY PRODUCES AN ABSTRACT SPECIFICATION OF A PHYSICAL SYSTEM AND A PROCESS FOR PRODUCING A PHYSICAL SYSTEM USING SUCH A TOOL," discloses a method of producing a functional description of an electronic circuit from the components of the integrated circuits and the interconnections between these components. It appears that the method of U.S. Pat. No. 5,734,572 requires that the exact implementation of a function be known before its function may be identified. The present invention does not require that the exact circuit implementation of a function be known before that function may be identified. The method of U.S. Pat. No. 5,734,572 appears to employ straight pattern matching between each function of the integrated circuit design and a library of known circuit implementations. The present invention does not require a library of known circuit implementations in order to identify functions of interest. U.S. Pat. No. 5,734,572 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,438,524, entitled "LOGIC SYNTHESIZER"; and U.S. Pat. No. 5,712,792, entitled "LOGIC CIRCUIT SYNTHESIZING METHOD UTILIZING BINARY DECISION DIAGRAM EXPLORED BASED UPON HIERARCHY OF CORRELATION BETWEEN INPUT VARIABLES"; each disclose a method of generating a layout for an integrated circuit from a functional description of the integrated circuit using pre-existing layouts for each function. The methods of U.S. Pat. Nos. 5,438,524 and 5,712,792 each create an integrated circuit layout from a functional description whereas the method of the present invention starts with a layout of an integrated circuit in transistor netlist form and generates a gate-level netlist therefrom. U.S. Pat. Nos. 5,438,524 and 5,712,792 are hereby incorporated by reference into the specification of the present invention.